package com.zyf.swordRefersOffer;
/**
 * 给定一个字符串 s ,找到 s 中最长的回文子串.你可以假设 s 的最大程度为 1000
 * 
 * 示例 1 :
 * 		输入 : "babad"
 * 		输出 : "bab"
 * 		注意 : "aba" 也是一个有效答案
 * 示例 2 :
 * 		输入 : "cbbd"
 * 		输出 : "bb"
 * 
 * @author lenovo
 * @Date 2020年7月8日
 * @Time 上午9:06:46
 */
public class _02_longestPalindrome {

	public static void main(String[] args) {
		String s = "cbbd";
		System.out.println(longestPalindrome(s));
	}
	/**
	 * 最长的回文子串方法
	 * @param s
	 * @return	回文子串
	 * 
	 * 解题思路 :
	 * 动态规划问题,定义 i , j ,两个指针,起始 i = k - 1 或者 k , j = k + 1;
	 * 假设回文子串为长度偶数的中位为 k = 0,如果 nums[i] != nums[j] ,则 k++;
	 * 否则 if(i >= 0) , i-- , j++ ,再次判断,直到不成立此时子串程度为 j - i - 1;
	 * 时间复杂度 O(log(n)*n)
	 */
	public static String longestPalindrome(String s) {
		int max = 1, mid = 0;//记录中位
		int i , j , k = 0;
		//回文子串为偶数
		while(k < s.length() - 1) {
			i = k;
			j = k + 1;
			while (i >= 0 && j < s.length() && compareNumber(i, j, s)) {
				compareNumber(i, j, s);
				i--;
				j++;
			}
			//i 多减了一次, j 多加了一次
			int len = j - i - 1;
			if (len > max) {
				max = len;
				mid = k;
			}
			k++;
		}
		//回文子串为奇数
		while(k < s.length() - 1) {
			i = k - 1;
			j = k + 1;
			while (i >= 0 && j < s.length() && compareNumber(i, j, s)) {
				compareNumber(i, j, s);
				i--;
				j++;
			}
			//i 多减了一次, j 多加了一次
			int len = j - i - 1;
			if (len > max) {
				max = len;
				mid = k;
			}
			k++;
		}
		if (max % 2 == 0) {
			return s.substring(mid - max / 2 + 1, mid + max / 2 + 1);
		}else {
			return s.substring(mid - max / 2, mid + max / 2 + 1);
		}
	}
	public static boolean compareNumber(int i, int j, String s) {
		if (s.charAt(i) != s.charAt(j)) {
			return false;
		}
		return true;
	}

}
